package 所有的题类.ZF.分治算法;

public class 多数元素 {

    public static int majorityElement(int[]nums){
        return divideAndMerge(nums,0,nums.length-1);
    }


    /**
     * 分支归并套路总结
     * 1，创建递归方法参数为【处理的对象，开始的位置，结束的位置】
     * 2，边界处理
     * 3，得到中间值
     * 4，递归方法处理左边处到中间值
     * 5，递归方法处理中间值的下一个到右边处
     * 6，边界处理
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public static int divideAndMerge(int[]nums,int left,int right){
        //结束递归的条件，当左边界和有边界指向同一个位置时，代表当前区间只有一个数字
        if(left==right){
            return nums[left];
        }
        //创建一个变量保存中间的位置
        int mid=(left+right)/2;
        //递归左区间
        int leftNum=divideAndMerge(nums,left,mid);
        int rightNum=divideAndMerge(nums,mid+1,right);
        //判断左右两个区间返回的值是否一样，如果一样，代表这个区间出现次数最后的数字就是leftNum
        if (leftNum == rightNum) {//左右两个区间一样
            return leftNum;
        }else{//左右两个区间的值不一样
            //需要判断leftNum和rightNum分别在此区间出现的次数，然后比较谁是多数元素
            int leftCount=intervalTimes(nums,leftNum,left,right);
            int rightCount=intervalTimes(nums,rightNum,left,right);
            return leftCount>rightCount?leftNum:rightNum;
        }
    }

    public static int intervalTimes(int[]nums,int num,int left,int right){
        //创建一个变量保存执行的数字在当前区间出现的次数
        int count=0;
        for (int i = left; i <=right; i++) {
            if(nums[i]==num){
                count++;
            }
        }
        //将次数返回
        return count;
    }
}
